1. Field of the Invention
This invention generally relates to methods of organizing information, particularly information related to semiconductor integrated circuit layouts, for use by computer programs that do automated design. More specifically, the invention relates to a method of restructuring and reorganizing information previously stored in bitmap or flat file physical design image form into a hierarchical data model form which provides more efficient storage and faster access to the data.
2. Description of Related Art
Computer assisted design (CAD) is generally well-known and relatively well-developed for a variety of applications, including general drafting, architectural, and other applications. CAD techniques are particularly suited for the design of mask or pattern layouts of integrated circuits due to the highly repetitive nature of such designs.
A particular type of CAD application is an automated design program. Such programs automatically select possible designs, preferably optimized designs, to meet the many critical design constraints which must be observed during the design process. Particularly in the integrated circuit design field, they are essential in producing reliable designs in a timely and cost-effective manner. Because of their wide use in the integrated circuit design field, this invention is described with particular emphasis on that field, although the invention finds application in other fields of design as well.
All automated design programs need to consider the physical characteristics of the object being designed. For example, in the design of a semiconductor device there may be one program to perform placement of semiconductor devices and another program to perform wiring between the devices. The placement application requires information as to target placement area, constraints on the placement area and legality information as to what placeable objects can be placed in what areas. The wiring program needs to understand location information such as pin and via locations, spacing constraints, and characteristics such as coupling coefficients.
The information that each automated design tool needs to perform its job is called "image" information. Different images are required for different applications, e.g. placement and wiring. To facilitate processing of the information, it is important that the images be represented compactly and in a form that is relatively easy to access.
Current design automation tools usually represent these images in flat bitmap type structures. In this type of representation, each coordinate or point of interest in a semiconductor package being designed is represented by a group of bits. Each group of bits contains information relating to the point to which the group corresponds. Each layer in the package is represented by a two-dimensional array of such groups of bits. To use the image, the design tool must process the data stored in the bit groups that correspond to the points within the area of interest.
This flat bitmap image structure does not provide the critical information in a form which is quick to process and easy to access. Nor does it meet the goal of efficient and compact storage. In particular, semiconductor devices are typically formed of repeated patterns, or patterns which are substantially repeated but modified to a greater or lesser extent in particular iterations of the pattern. In the usual bitmap form, the information about each of the repeated patterns is repeated for every iteration of the pattern. The processing and handling of the large amount of data coupled with the design rules which must be satisfied, impose severe time penalties on the computer processing and slow the automated design process unacceptably.
To alleviate this problem and improve the efficiency of data access it is known to select different types of data structures which may be better suited for the desired task. For example, it is recognized in the data processing arts that operation of an application program can often be enhanced by the data structure employed to hold data upon which the application program will operate. When a search of data is required, tree structures will increase search speed since, if properly managed and rebalanced from time to time, a tree structure will permit a portion of the data remaining to be searched to be ignored subsequent to each search path decision.
However, during computer assisted design of integrated circuits, in particular, the amount of data which is generated and the number of operations to be performed thereon is sufficient to significantly slow the response time of the data processing apparatus even if such known data structures are optimally used. This is because the management of the data structure itself requires a significant amount of computation overhead. Further, no single data structure is optimum for all applications or even all parts of a single application.
Of course, techniques are known for manipulating data structures such as for rebalancing of tree structures and rearranging data in one data structure into another data structure. That is, flat (e.g. all image points represented without regard to relative position), segmented or slotted (e.g. where restrictions are placed on locations of sub-patterns) and the like can be freely translated to other data structures such as tree structure within the present state of the art, but only at the cost of substantial computing overhead. Running such translation programs in the foreground, or even under general control of the design program does not engender efficiency, when a large amount of data is involved.
A substantial loss of efficiency accrues as increasing amounts of data are generated during the design process, particularly in the case of integrated circuit design. This can be appreciated by observing that the benefit of tree structures is that they allow substantial amounts of data to be ignored during the search of that data. Manipulating each piece of data in the database, or even a significant fraction thereof, to allow an efficient search, clearly would require more data processing time then is saved by an optimally efficient search.
One data structure that has been used in integrated circuit design applications is a hierarchical quad tree model. In this model, each area of the bitmap image is divided up into pieces by quadsection, i.e., by repeatedly splitting each area into four equal pieces, until the entire image area is divided down to the desired granularity.
The result of the repeated splitting is to provide an area tree. The topmost node of the tree corresponds to the entire image. The next level contains four nodes, corresponding to four equal quadrants of the image. The next level contains sixteen nodes, four connected to each of the four quadrant nodes at the level above, and each corresponding to one fourth of the area of its quadrant, i.e., one sixteenth of the entire area. The splitting of each sub-area into four pieces continues until the final smallest areas are reached at the desired granularity level.
While this hierarchical area organization can improve data handling when coupled with appropriately designed automation tools, its rigidly fixed quad structure introduces many inefficiencies. Principally, the quad tree hierarchical arrangement and other hierarchical models which use fixed structures, fail to consider the characteristics of different regions in the dividing process, and fail to identify repeated patterns that do not match the fixed structure, thereby losing storage efficiency as compared to an optimized model that stores common information about repeated patterns in a single shared location.
A related problem with fixed structure models is in the failure to provide rapid access to the information for all access patterns. The fixed structure model tends to require longer searches for information than would be needed if the model considered the underlying physical characteristics and layout of the package in a form that is specialized for a type of application. The constraints imposed by the data structure and the modeling of the physical structure being designed, are a major impediment to the operational efficiency of computer assisted design applications.
Accordingly, there is a long felt need for transforming physical image data into a form which provides efficient access to data during computer assisted design processing. Meeting this need is one object of the present invention.
Another object of the present invention is to provide a method of hierarchically organizing data in an image which relates to the technology underlying the circuit elements or components of the image. This corresponds the model more closely to the physical reality and permits use of the model at an earlier design stage when the technology is being selected to meet the requirements of the device being designed.
Yet another object of the present invention is to provide a method for restructuring physical design images into hierarchical data models which allows different restructuring criteria to be used to optimize the hierarchical model for use by different application programs.
Yet another object of the invention is to provide a method of generating a hierarchical data model from a physical design image which hides the details of the areas being represented at lower layers from design application programs which do not need to access those details.
A further object of the invention is to provide for data sharing to reduce the total amount of data stored by providing constructs which reuse information that is common between different entities.